/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/sparse-matrix-multiplication
   @Language: C++
   @Datetime: 19-06-12 16:08
   */

class Solution {
public:
	/**
	 * @param A: a sparse matrix
	 * @param B: a sparse matrix
	 * @return: the result of A * B
	 */
	vector<vector<int> > multiply(vector<vector<int> > &A, vector<vector<int> > &B) {
		// write your code here
		int ra=A.size(), ca=A[0].size(), rb=B.size(), cb=B[0].size();
		vector<vector<int> > C(ra,vector<int>(cb,0));
		for(int i=0; i<ra; ++i)
			for(int j=0; j<cb; ++j)
				for(int k=0; k<ca; ++k)
					C[i][j]+=A[i][k]*B[k][j];
		return C;
	}
};
